﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;

public class MixingColors
{
    public List<string> updateStr(int[] colors)
    {
        List<string> newStrList = new List<string>();
        foreach (int c in colors)
        {
            newStrList.Add(Convert.ToString(c, 2).PadLeft(12, '0'));
        }
        return newStrList;
    }

    public int minColors(int[] colors)
    {
        int[] sorted = colors.OrderByDescending(p=>p).ToArray();
        int len = sorted.Length, res = 0;
        List<string> strList = new List<string>();
        strList = updateStr(sorted);
        int r = 0, c= 30;

        while (c >= 0 ) {
            if ((sorted[r] & (1 << c)) == 0)
            {
            }
            else
            {
                for (int row2 = r + 1; row2 < len; row2++)
                {
                    if ((sorted[row2] & (1 << c)) > 0)
                    {
                        sorted[row2] ^= sorted[r];
                        strList = updateStr(sorted);
                    }
                }
                sorted = sorted.OrderByDescending(p => p).ToArray();
                strList = updateStr(sorted);
                r++;
            }
            if (r == len - 1) break;
            c--;
        }
        for (int i = 0; i < len; i++)
        {
            if (sorted[i] != 0) res++;
        }
        return res;
    }

    public int minColors2(List<int> colors)
    {
        colors.Sort();
        int len = colors.Count, res = 0;
        List<string> strList = new List<string>();
        strList = updateStr(colors.ToArray());
        for (int i = 0; i < len; i++)
        {
            for (int bit = 30; bit >= 0; bit--)
            {
                for (int j = i + 1; j < len; j++)
                {
                    if ((colors[i] & (1 << bit)) > 0)
                    {
                        if ((colors[j] & (1 << bit)) > 0)
                        {
                            colors[j] ^= colors[i];
                            strList = updateStr(colors.ToArray());
                        }
                    }
                }
            }
        }

        for (int i = 0; i < len; i++)
        {
            if ( colors[i] != 0 ) res ++;
        }
        return res;
    }
}


public class NumbersChallenge
{
    public int MinNumber(int[] S)
    {
        int sum = 0;
        int[] sorted = S.OrderBy(p=>p).ToArray();
        for (int i = 0; i < sorted.Count(); i++)
        {
            if (sorted[i] > sum + 1)
            {
                return (sum + 1);
            }
            else
            {
                sum = sum + sorted[i];
            }
        }
        return (sum + 1);
    }
    public int MinNumber2(int[] S)
    {
        bool[] foundArray = new bool[100000];
        foreach (var sArray in GetPowerSet(S.ToList()))
        {
            int idx = sArray.Sum();
            if ( idx < 100000 ) foundArray[idx] = true;
        }

        for (int i = 1; i < 100000; i++)
        {
            if (!foundArray[i]) return i; 
        }
        return 0;
    }

    public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
    {
        return from m in Enumerable.Range(0, 1 << list.Count)
               select
                   from i in Enumerable.Range(0, list.Count)
                   where (m & (1 << i)) != 0
                   select list[i];
    }
}



public class TwoWaysSorting
{
    public string sortingMethod(string[] stringList)
    {
        string[] lexSort = stringList.OrderBy(p => p).ToArray();
        string[] lenSort = stringList.OrderBy(p => p.Length).ToArray();

        bool isLex = true;
        bool isLen = true;
        for (int i = 0; i < stringList.Length; i++)
        {
            if (lexSort[i] != stringList[i]) isLex = false;
            if (lenSort[i] != stringList[i]) isLen = false;
        }

        if (isLex && isLen) return "both";
        else if (isLex && !isLen) return "lexicographically";
        else if (!isLex && isLen) return "lengths";
        return "none";
    }
}

